27/02/2021

Desenho do Algoritmo

  • Testes dos Espaços:
    • Espaços discretos menores que \(M_{(8,8)}\) não apresentaram solução ótima.
    • Espaços maiores que \(M_{(150,150)}\) apresentaram custo computacional muito elevado.
  • Implementação:
    • O algorítimo foi desenhado para escanear os espaços discretos de \(M_{(8,8)}\) até \(M_{(150,150)}\) na área de 800 x 800 com intervalos iguais entre os pontos.
    • Para ilustrar, foi considerado o espaço de \(M_{(9,9)}\), que representa 81 possíveis localizações para os Pa’s.

Gráfico do Espaço de Busca

Iterações do Algoritmo

  • Laço:
    • A cada iteração o algoritmo inspeciona cada coordenada do espaço discretizado de possíveis localizações dos Pa’s e determina o PA que cobre o maior número de Pd’s.
    • Se a condição de 150 Mbps não for violada, o índice do PA com maior cobertura de Pd’s é armazenado e esses Pd’s são removidos.
    • O algoritmo reinicia a busca do próximo PA que cobre mais Pd’s dentre os restantes.
  • Critério de Parada:
    • O algoritmo para quando cobre pelo menos 475 dos 500 Pd’s atendendo as restrições de consumo de banda e limite de Pa’s.

Primeira Iteração

  • O algoritmo conta o número de Pd’s cobertos por cada uma das 81 possíveis localizações para o 1º PA e soma os Mbps demandados.

  • O máximo de 202 Pd’s são cobertos pelo PA nas coordenadas (200, 200).

  • O total de 146 Mbps de demanda desses Pd’s não viola a condição de menor que 150 Mbps.

  • As coordenadas deste 1º PA são armazenadas.

  • Os 202 Pd’s cobertos por este PA são removidos por já estarem cobertos.

Segunda Iteração

  • O algoritmo realiza a mesma busca e contagem da primeira iteração, porém desconsiderando os Pd’s cobertos pelo 1º PA.

  • O máximo de 199 Pd’s são cobertos pelo PA nas coordenadas (600, 600).

  • O total de 141 Mbps de demanda destes Pd’s não viola a condição de menor que 150 Mbps.

  • Da mesma forma são armazenadas as coordenadas desse 2º PA.

  • Os 199 Pd’s cobertos por este PA também são removidos por já estarem cobertos.

Decima Sétima Iteração

  • O algoritmo para.

  • O resultado da busca retorna uma solução no mínimo local de 17 PA´s.

  • A condição de que sejam cobertos 95% ou 475 do total de 500 Pd’s é atendida.

  • A restrição de número de Pa’s menor que 100 é atendida.

  • A restrição de que a soma da demanda dos Pd’s cobertos por um Pa não exceda 150 Mbps é atendida.

  • As informações dos índices, número de Pd’s atendidos e total da demanda em Mbps de cada Pa podem ser recuperadas.